/*
 * Copyright (c) 2020.版权所有高金磊
 */

package 领扣算法.A简单题.使用最小花费爬楼梯_优化;

import Tools.SimpleTimeTest;

public class Main {
    //可以但是超时
    public int minCostClimbingStairs(int[] cost) {

        return Math.max(plus(cost, 0),plus(cost, 1));
    }
    int plus(int[] cost,int step){
        if (step>cost.length-1)
            return 0;
        return Math.min(cost[step]+plus(cost, step+1),cost[step]+plus(cost, step+2));

    }
    public static void main(String arg[]){//main--来自高金磊
        SimpleTimeTest.TestMethod();
        new Main().minCostClimbingStairs(new int[]{841,462,566,398,243,248,238,650,989,576,361,126,334,729,446,897,953,38,195,679,65,707,196,705,569,275,259,872,630,965,978,109,56,523,851,887,91,544,598,963,305,481,959,560,454,883,50,216,732,572,511,156,177,831,122,667,548,978,771,880,922,777,990,498,525,317,469,151,874,202,519,139,670,341,514,469,858,913,94,849,839,813,664,163,3,802,21,634,944,901,446,186,843,742,330,610,932,614,625,169,833,4,81,55,124,294,71,24,929,534,621,543,417,534,427,327,179,90,341,949,368,692,646,290,488,145,273,617,596,82,538,751,80,616,763,826,932,184,630,478,163,925,259,237,839,602,60,786,603,413,816,278,4,35,243,64,631,405,23,638,618,829,481,877,756,482,999,973,718,157,262,752,931,882,741,40,77,535,542,879,607,879,321,46,210,116,244,830,591,285,382,925,48,497,913,203,239,696,162,623,291,525,950,27,546,293,108,577,672,354,256,3,671,998,22,989,557,424,251,923,542,243,46,488,80,374,372,334,190,817,150,742,362,196,75,193,162,645,859,758,433,903,199,289,175,303,475,818,213,576,181,668,243,297,572,549,840,161,29});
        SimpleTimeTest.endMethod("");

    }
}
